package a3_edmonds_karp;

import java.util.ArrayList;

import a1_graph_lib.AIGraph;
import a1_graph_lib.AIGraphCounter;
import a1_graph_lib.Edge;
import a2_bellman_ford.Bellman_Ford_Algorithmus;

public class Edmonds_Karp {
	// --------------------STRING KONSTANTEN---------------------------
	// Kostenattribute
	private static final String KOSTEN = "Kosten";
	// Vorgaenger
	private static final String VORGAENGER = "Vorgaenger";
	// Die Kantenkapazitaet
	private static final String CAPACITY = "Kapazitaet";
	// Der aktuelle Fluss in der Kante
	private static final String ACTUAL_FLOW = "aktuellerFluss";
	// FLUSS IN ANDERE RICHTUNG
	private static final String ACTUAL_OPPOSITE_FLOW = "gegenFluss";
	// Bezeichnung des Standartattributes (vorgegeben durch den Reader)
	private static final String STANDART = "0";
	// NAME DES ATTRIBUTES
	private static final String NAME = "NAME";
	// --------------------VOLL?------------------------
	// Check, ob die Kante keine Kapazitaet mehr hat wird hierunter gespeichert
	private static final String ISFULL = "Voll";
	// Varianten um ISFULL zu benutzen
	private static final String YES = "ja";
	private static final String NO = "nein";
	// -------------------------------------------------
	// ------------------VOR- oder RUECKWAERTS----------
	private static final String DIRECTION = "RICHTUNG";
	private static final String FORWARD = "VOR";
	private static final String BACKWARD = "ZURUECK";	
	// -------------------------------------------------
	// REST
	private static final String REST = "REST";
	// --------------------------INT KONSTANTEN---------------------------------
	// Maximaler INT
	private static final int MAXINT = Integer.MAX_VALUE;
	// Konstante fuer die Initialisierung des aktuellen Flusses
	private static final int ZERO = 0;
	// Konstante fuer die Initialisierung des Attributwertes
	private static final int INITATTR = 1;
	
	// ----------------------INT VARIABLEN------------------------------------------
	// globale Variable fuer die Speicherung des maximalen Flusses jeweils jeden Pfades
	private static int maxFlow = MAXINT;
	private static int maxFlowGraph = 0;
	
	private static void init_for_Bf(AIGraphCounter graph) {
		ArrayList<Integer> edges = graph.getEdges();
		int verticesOfGraph = graph.getVertices().size();
		int edgesOfGraph = graph.getEdges().size();
		System.out.println("Der Graph hat " + verticesOfGraph + " Knoten!");
		System.out.println("Der Graph hat " + edgesOfGraph + " Kanten!");
		System.out.println();

		for (Integer edge : edges) {
			// Initialisierung des Attributwertes auf 1
			setKosten(graph, edge, INITATTR);
			// Initialisierung des aktuellen Flusses auf 0
			setActualFlow(graph, edge, ZERO);
			// Initialisierung des "Full-Checks" auf NEIN
			setIsfull(graph, edge, NO);
			// Initialisierung der Richtung
			setDirection(graph, edge, FORWARD);
			// Initialisierung der Kapazitaet 
			setCapacity(graph, edge, graph.getValE(edge, STANDART));
			// Initialisierung des Restwertes
			setRest(graph, edge, calcRest(graph, edge));
		}

	}
	
	// hier wird der kuerzeste Pfad durch Bellman-Ford bestimmt
	private static ArrayList<Integer> shortestPath(AIGraphCounter graph, int quelle,int senke) {
		// Neue Liste um die Kanten des kuerzesten Pfades abzulegen
		ArrayList<Integer> shortestPathEdges = new ArrayList<Integer>();
		// Ausfuehren des Bellman_Ford. Rueckgabewert ist ein Graph mit dem Attribut Vorgaenger
		graph = Bellman_Ford_Algorithmus.bellmanFord(graph, quelle, KOSTEN);
		int vertex = senke;
		// Wenn
		// Die Kosten des Knotens sind groesser als die Anzahl der Kanten im Graphen und
		// wenn es keinen Vorgaenger gibt dann wird die Schleife nicht ausgefuehrt
		if(vertex != MAXINT && graph.getValV(vertex, KOSTEN) <= graph.getEdges().size()) {
			// So lange wie der aktuellen Knoten nicht die Quelle ist, wird die Whileschleife abgelaufen
			while(vertex != quelle){
				// Alle Kanten die vom Vorgaengerknoten wegfuehren in einer Liste
				ArrayList<Integer> temp = graph.getIncident(graph.getValV(vertex, VORGAENGER));	
				// aus denen sucht man hier den heraus, der zum Nachfolger geht und speichert ihn in der 
				// Liste des kurzen Weges 
				for (Integer incidentEdge : temp) {
					if (graph.getTarget(incidentEdge) == vertex) {
						shortestPathEdges.add(incidentEdge);
						// Bestimmung vom maximalen Fluss. Dazu wird jede Kapazitaet des Pfades mit dem bisher
						// maximalen Wert verglichen. Ist er kleiner wird er uebernommen.
						int rest = getRest(graph, incidentEdge);
						if(rest < maxFlow){
							maxFlow = rest;
						}
					}
				}
				// vertex umsetzen
				vertex = graph.getValV(vertex, VORGAENGER);
			}	
		}
		
		return shortestPathEdges;
	}
	
	private static AIGraphCounter edmondsKarp(AIGraphCounter graph, int quelle, int senke){
		
		// Uebergabe der Liste von Kanten, die den kuerstesten Weg bilden
		ArrayList<Integer> actualPath = shortestPath(graph, quelle, senke);
		// Solange noch Wege gefunden werden
		int counter = 0;
		while (!(actualPath.isEmpty())) {
			counter++;
			for(Integer edge:actualPath){
				// VORWAERTSKANTEN
//				if(getDirection(graph, edge) == FORWARD){
				setActualFlow(graph, edge, addFlow(graph, edge));
				setRest(graph,edge,calcRest(graph, edge));
//				}else if(getDirection(graph, edge) == BACKWARD){
//				setActualOppositeFlow(graph, edge, addFlow(graph, edge));
//				}else{
//				System.out.println("UNGUELTIGE RICHTUNG");
//				}
				// Wenn Kapazitaet erschoepft, dann wird der Attributwert KOSTEN hochgesetzt und
				// die Kante als VOLL markiert
				if(checkRest(graph, edge)){
					setKosten(graph, edge, (2 * (graph.getEdges().size())) + 1);
					setIsfull(graph, edge, YES);	
				}else if ((getIsfull(graph, edge) == YES) && checkRest(graph, edge) == false) {
					// WENN eine Kante nicht mehr VOLL ist, dann wird sie wieder in die kurze Wege
					// berechnung eingebunden, dafuer werden die Kosten wieder auf 1 gesetzt
					setKosten(graph, edge, INITATTR);
					setIsfull(graph, edge, NO);
				}
				// RUECKWAERTSKANTEN
				// Knoten vertauschen, fuer Pruefung auf entgegengesetzte Ecke
				int newTarget = graph.getSource(edge);
				int newSource = graph.getTarget(edge);
				// Kanten die aus der neuen Quelle der Kante hinausgehen
				ArrayList<Integer> checkNewEdge = graph.getIncident(newSource);
				
				boolean check = false;
				int oppositeEdge = ZERO;
				// Wenn es schon eine Verbindung von newSource zu newTarget gibt, dann wird keine neue
				// Kante erzeugt, sondern die Bestehende mit Attributen befuettert.
				for (Integer checkId : checkNewEdge) {
					if (graph.getTarget(checkId) == newTarget) {
						check = true;
						oppositeEdge = checkId;
						setCapacity(graph, oppositeEdge, getCapacity(graph, edge));
						// Wenn die Vorwaertskante voll ist, dann ist die Rueckwaertskante leer
						if(checkRest(graph, edge)){
							setActualOppositeFlow(graph, oppositeEdge, ZERO);
							setRest(graph, oppositeEdge, calcOppositeRest(graph,edge));
							// Wenn die Vorwaertskante nicht voll ist, dann ist der Flow dort
							// wie der Rest der Vorwaertskante
						}else{
							setActualOppositeFlow(graph, oppositeEdge, getRest(graph, edge));
							setRest(graph, oppositeEdge, calcOppositeRest(graph,edge));
						}
					}
				} 
				// Wenn die Kante noch nicht vorhanden ist, wird eine neue erzeugt	
				// AUCH DIE KOSTEN ZUWEISEN! 1 wenn verfuegbar; hoch wenn nicht
				if(!(check)){
					int edgeId = graph.addEdgeD(newSource, newTarget);
					// Kosten setzen
					setKosten(graph, edgeId, INITATTR);
					// Gleiche Kapazitaet wie die Vorwaertskante
					setCapacity(graph, edgeId, getCapacity(graph, edge));
					// Rueckwaertskante markieren
					setDirection(graph, edgeId, BACKWARD);
					// REST
					if(checkRest(graph, edge)){
						setActualOppositeFlow(graph, edgeId, ZERO);
						setRest(graph, edgeId, calcOppositeRest(graph, edgeId));
					// Wenn die Vorwaertskante nicht voll ist, dann ist der Flow dort
					// wie der Rest der Vorwaertskante
					}else{
						setActualOppositeFlow(graph, edgeId, getRest(graph, edge));
						setRest(graph, edgeId, calcOppositeRest(graph, edgeId));
					}
				}
			}	
			// Zuruecksetzen der Knotenattribute als Vorbereitung auf neuen BF durchlauf
			ArrayList<Integer>vertices = graph.getVertices();
			for(Integer vertex:vertices){
				graph.setValV(vertex, KOSTEN, MAXINT);
				graph.setValV(vertex, VORGAENGER, MAXINT);
			}
			maxFlow = MAXINT;
			System.out.println("Wegsuche Lauf " + counter + ": ");
			printPath(graph, actualPath);
			System.out.println();
			actualPath = shortestPath(graph, quelle, senke);
		}
		return graph;
	}
	// HAUPTALGORITHMUS	
	public static AIGraphCounter runEdmondsKarp(AIGraphCounter graph, int quelle, int senke){
		// INITIALISIEREN
		init_for_Bf(graph);
		// ALGORITHMUS AUSFUEHREN
		edmondsKarp(graph, quelle, senke);
		// GRAPHEN VON RUECKWAERTSKANTEN BEFREIEN
		cleanGraph(graph);
//		// AUSGEBEN
		calcMaxFlow(graph, quelle);
		return graph;
	}
	
	private static AIGraphCounter cleanGraph(AIGraphCounter graph){
		ArrayList<Integer> edges = graph.getEdges();
		for(Integer edgeId:edges){
			if(getDirection(graph, edgeId) == BACKWARD){
				int von = graph.getSource(edgeId);
				int nach = graph.getTarget(edgeId);
				graph.deleteEdge(von, nach);
			}
		}
		return graph;
	}
	
	public static int calcMaxFlow(AIGraphCounter graph, int quelle){
		maxFlowGraph = 0;
		ArrayList<Integer> outOfQuelle = graph.getIncident(quelle);
		System.out.println("###################################################");
		System.out.println("Kanten die aus der Quelle fuehren: " + outOfQuelle);
		for(Integer edge:outOfQuelle){
			int tempFlow = getActualFlow(graph, edge);
			System.out.println("KANTE " + edge + " hat den Fluss: " + tempFlow);
			maxFlowGraph = maxFlowGraph + tempFlow;
		}
		System.out.println("Maximaler Fluss des Graphen: " + maxFlowGraph);
		System.out.println();
		System.out.println("Zugriffe auf die Knoten: " + graph.getZugriffeLesenVerticis());
		System.out.println("Zugriffe auf die Kanten: " + graph.getZugriffeLesenEdges());
		System.out.println("Zugriffe auf die Attribute (auslesen): " + graph.getZugriffeLesenAtribute());
		System.out.println("Zugriffe auf die Attribute (schreiben): " + graph.getZugriffeAendernAtribute());
		System.out.println("Zugriffe insgesamt: " + graph.getZugriffeGraph());
		System.out.println();
		System.out.println("###################################################");
		return maxFlowGraph;
	}
	
	private static void printPath(AIGraphCounter graph, ArrayList<Integer> list){
		int size = list.size();
		if(size == 0){
			System.out.println("LISTE LEER");
		}else{
			for(int e = size-1; e >= 0; e--){
				int edgeId = list.get(e);
				int sourceVertex = graph.getSource(edgeId);
				int targetVertex = graph.getTarget(edgeId);
				String sourceName = graph.getStrV(sourceVertex, NAME);
				String targetName = graph.getStrV(targetVertex, NAME);
				int flow = getActualFlow(graph, edgeId);
				int max = getCapacity(graph, edgeId);
				System.out.println("Pfad: Von " + sourceName + " nach " + targetName + " KantenID: " + edgeId + " mit dem Fluss: " + flow + " mit dem Maximum: " + max);
				
			}			
		}
	}
	
	// KAPAZITAET -------------------------------------------
	private static int getCapacity(AIGraphCounter graph, int edge){
		int kapazitaet = graph.getValE(edge, CAPACITY);
		return kapazitaet;
	}
	
	private static void setCapacity(AIGraphCounter graph, int edge, int val){
		graph.setValE(edge, CAPACITY, val);
	}
	
	// AKTUELLER FLUSS --------------------------------------
	private static int getActualFlow(AIGraphCounter graph, int edge){
		int actualFloat = graph.getValE(edge, ACTUAL_FLOW);
		return actualFloat;
	}
	
	private static void setActualFlow(AIGraphCounter graph, int edge, int val){
		graph.setValE(edge, ACTUAL_FLOW, val);
	}
	
	// FLUSS aufaddieren
	private static int addFlow(AIGraphCounter graph, int edge){
		// Aktueller Fluss an der Kante
		int old = getActualFlow(graph, edge);
		// kleinster Fluss an dem Pfad
		int aktuellFluss = maxFlow;
		// Errechneter neuer Wert
		int newFloat = old + aktuellFluss;
		return newFloat;
	}
	
	// GEGENFLUSS
	private static int getActualOppositeFlow(AIGraphCounter graph, int edge) {
		int oppFloat = graph.getValE(edge, ACTUAL_OPPOSITE_FLOW);
		return oppFloat;
	}
	
	private static void setActualOppositeFlow(AIGraphCounter graph, int edge, int val){
		graph.setValE(edge, ACTUAL_OPPOSITE_FLOW, val);
	}
	
	// REST ------------------------------------------------
	// REST DER VORWAERTSKANTEN BERECHNEN
	private static int calcRest(AIGraphCounter graph, int edge) {
		int kapazitaet = getCapacity(graph, edge);
		int fluss = getActualFlow(graph, edge);
		
		int rest = kapazitaet - fluss;
		return rest;
	}
	// REST DER RUECKWAERTSKANTEN BERECHNEN
	private static int calcOppositeRest(AIGraphCounter graph, int edge){
		int kapazitaet = getCapacity(graph, edge);
		int fluss = getActualOppositeFlow(graph, edge);
		
		int rest = kapazitaet - fluss;
		return rest;
	}
	// DEN REST SETZEN
	private static void setRest(AIGraphCounter graph, int edge, int val) {
		graph.setValE(edge, REST, val);
	}
	
	//DEN REST "HOLEN"
	private static int getRest(AIGraphCounter graph, int edge){
		int rest = graph.getValE(edge, REST);
		return rest;
	}
	// Restkapazitaet ueberpruefen
	private static boolean checkRest(AIGraphCounter graph, int edge){
		boolean full;
		if (graph.getValE(edge, REST) == 0) {
			full = true;
		}else{
			full = false;
		}
		return full;
	}
	// KOSTEN -----------------------------------------------
	
	// DIE KOSTEN HOLEN
	@SuppressWarnings("unused")
	private static int getKosten(AIGraphCounter graph, int edge){
		int kosten = graph.getValE(edge, KOSTEN);
		return kosten;
	}
	
	// DIE KOSTEN SETZEN
	private static void setKosten(AIGraphCounter graph, int edge, int val){
		graph.setValE(edge, KOSTEN, val);
	}
	// VOLL --------------------------------------------------
	
	// ISFULL ATTRIBUT "HOLEN"
	private static String getIsfull(AIGraphCounter graph, int edge){
		String state = graph.getStrE(edge, ISFULL);
		return state;
	}
	
	// ISFULL ATTRIBUT SETZEN
	private static void setIsfull(AIGraphCounter graph, int edge, String val){
		graph.setStrE(edge, ISFULL, val);
	}
	// RICHTUNG -----------------------------------------------
	
	// RICHTUNG "HOLEN"
	private static String getDirection(AIGraphCounter graph, int edge){
		String dir = graph.getStrE(edge, DIRECTION);
		return dir;
	}
	
	// RICHTUNG SETZEN
	private static void setDirection(AIGraphCounter graph, int edge, String val){
		graph.setStrE(edge, DIRECTION,val);
	}
}
